package com.asa.hutils;
/**
 * 	多项式相乘
 * @author Administrator
 *
 */
public class NTT {
	
	
	 
	int N = 1 << 18;
	int P = (479 << 21) + 1;
	int G = 3;
	int NUM = 20;
	 
	double  wn[] = new double[NUM];
	double  a[] = new double[N];
	double b[] = new double[N];
	
	char A[] = new char[N];
	char B[] = new char[N];
	 
	double quick_mod(int a, int b, int m)
	{
		double ans = 1;
	    a %= m;
	    while(b!=0)
	    {
	        if((b & 1)!=0)
	        {
	            ans = ans * a % m;
	            b--;
	        }
	        b = b>>1;
	        a = a * a % m;
	    }
	    return ans;
	}
	 
	void GetWn()
	{
	    for(int i = 0; i < NUM; i++)
	    {
	        int t = 1 << i;
	        wn[i] = quick_mod(G, (P - 1) / t, P);
	    }
	}
	 
	void Prepare(char A[], char B[], double a[], double b[], int len)
	{
	    len = 1;
	    int L1 = A.length;
	    int L2 = B.length;
	    while(len <= 2 * L1 || len <= 2 * L2) len <<= 1;
	    for(int i = 0; i < len; i++)
	    {
	        if(i < L1) a[i] = A[L1 - i - 1] - '0';
	        else a[i] = 0;
	        if(i < L2) b[i] = B[L2 - i - 1] - '0';
	        else b[i] = 0;
	    }
	}
	 
	void Rader(double a[], int len)
	{
	    int j = len >> 1;
	    for(int i = 1; i < len - 1; i++)
	    {
	        if(i < j) swap(a,i,j);
	        int k = len >> 1;
	        while(j >= k)
	        {
	            j -= k;
	            k >>= 1;
	        }
	        if(j < k) j += k;
	    }
	}
	 
	private void swap(double[] a,int i, int j) {
		// TODO Auto-generated method stub
		double asa = a[i];
		a[i] = a[j];
		a[j] = asa;
	}

	void NTT(double a[], int len, int on)
	{
	    Rader(a, len);
	    int id = 0;
	    for(int h = 2; h <= len; h <<= 1)
	    {
	        id++;
	        for(int j = 0; j < len; j += h)
	        {
	            double w = 1;
	            for(int k = j; k < j + h / 2; k++)
	            {
	                double u = a[k] % P;
	                double t = w * a[k + h / 2] % P;
	                a[k] = (u + t) % P;
	                a[k + h / 2] = (u - t + P) % P;
	                w = w * wn[id] % P;
	            }
	        }
	    }
	    if(on == -1)
	    {
	        for(int i = 1; i < len / 2; i++)
//	            swap(a[i], a[len - i]);
	        	swap(a, i,len-i);
	        double inv = quick_mod(len, P - 2, P);
	        for(int i = 0; i < len; i++)
	            a[i] = a[i] * inv % P;
	    }
	}
	 
	void Conv(double a[], double b[], int n)
	{
	    NTT(a, n, 1);
	    NTT(b, n, 1);
	    for(int i = 0; i < n; i++)
	        a[i] = a[i] * b[i] % P;
	    NTT(a, n, -1);
	}
	 
	void Transfer(double a[], int n)
	{
	    double t = 0;
	    for(int i = 0; i < n; i++)
	    {
	        a[i] += t;
	        if(a[i] > 9)
	        {
	            t = a[i] / 10;
	            a[i] %= 10;
	        }
	        else t = 0;
	    }
	}
	 
//	void Print(double a[], int n)
//	{
//	    boolean flag = true;
//	    for(int i = n - 1; i >= 0; i--)
//	    {
//	        if(a[i] != 0 && flag)
//	        {
//	            //使用putchar()速度快很多
//	            putchar(a[i] + '0');
//	            flag = false;
//	        }
//	        else if(!flag)
//	            putchar(a[i] + '0');
//	    }
//	    puts("");
//	}

	public static void main(String[] args) {
		
		
		
		
	}
	
	
	
}
